class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        self.memo = dict()

        def dp(t1, i,  t2, j):
            if (i, j) in self.memo:
                return self.memo[(i, j)]
            
            if i >= len(text1) or j >= len(text2):
                return 0
            
            res = 0
            if t1[i] == t2[j]:
                res = dp(t1, i+1, t2, j+1) + 1
            else:
                res = max(dp(t1, i, t2, j+1),
                        dp(t1, i+1, t2, j))
            self.memo[(i, j)] = res
            return res
        
        dp(text1, 0, text2, 0)
        return self.memo[(0, 0)]


            
if  __name__ == '__main__':
    s = Solution()
    res = s.longestCommonSubsequence("abc", "ac")
    print(res)